/**
 * 21. 合并两个有序链表
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */
const {
  createListNode,
  displayListNode,
} = require('../../libs/public');

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
function mergeTwoLists(list1, list2) {
  if (!list1) return list2;
  if (!list2) return list1;
  let head1 = list1;
  let head2 = list2;
  let newHead;
  if (head1.val < head2.val) {
    newHead = head1;
    head1 = head1.next;
  } else {
    newHead = head2;
    head2 = head2.next;
  }
  let cur = newHead;
  while (head1 && head2) {
    if (head1.val < head2.val) {
      cur.next = head1;
      head1 = head1.next;
    } else {
      cur.next = head2;
      head2 = head2.next;
    }
    cur = cur.next;
  }
  let leftHead = head1 || head2;
  while (leftHead) {
    cur.next = leftHead;
    leftHead = leftHead.next;
    cur = cur.next;
  }
  return newHead;
}

console.log(displayListNode(mergeTwoLists(createListNode([1, 2, 4]), createListNode([1, 3, 4]))) === '[1,1,2,3,4,4]');
console.log(displayListNode(mergeTwoLists(createListNode([]), createListNode([]))) === '[]');
console.log(displayListNode(mergeTwoLists(createListNode([]), createListNode([0]))) === '[0]');
